from collections import Counter, defaultdict
from typing import List

import numpy as np


class Solution:
    def maxDistance(self, arrays: List[List[int]]) -> int:
        minimum = float("inf")
        maximum = float("-inf")
        ans = -1
        for array in arrays:
            ans = max(ans, maximum - array[0], array[-1] - minimum)
            maximum = max(maximum, array[-1])
            minimum = min(minimum, array[0])
        return ans

    def wiggleSort(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        nums.sort()
        for i in range(1, len(nums) - 1, 2):
            nums[i], nums[i + 1] = nums[i + 1], nums[i]

    def reverseWords(self, s: List[str]) -> None:
        """
        Do not return anything, modify s in-place instead.
        """

        def reverse(i, j):
            while i < j:
                s[i], s[j] = s[j], s[i]
                i, j = i + 1, j - 1

        i, j = 0, 0
        n = len(s)
        while i < n:
            j = i
            while j < n and s[j] != " ":
                j += 1
            reverse(i, j - 1)
            i = j + 1
        reverse(0, n - 1)

    def anagramMappings(self, nums1: List[int], nums2: List[int]) -> List[int]:
        idx_map = {v: i for i, v in enumerate(nums2)}
        for i in range(len(nums1)):
            nums1[i] = idx_map[nums1[i]]
        return nums1

    def canPermutePalindrome(self, s: str) -> bool:
        cnt = Counter(s)
        odd_shown = False
        for v in cnt.values():
            if v & 1:
                if odd_shown:
                    return False
                odd_shown = True
        return True

    def areSentencesSimilar(self, sentence1: List[str], sentence2: List[str], similarPairs: List[List[str]]) -> bool:
        m, n = len(sentence1), len(sentence2)
        if m != n:
            return False
        dic = defaultdict(set)
        for u, v in similarPairs:
            dic[u].add(v)
        for word1, word2 in zip(sentence1, sentence2):
            if word2 != word1 and word2 not in dic[word1]:
                return False
        return True

    def calculateTime(self, keyboard: str, word: str) -> int:
        idx_map = {v: i for i, v in enumerate(keyboard)}
        i = 0
        ans = 0
        for c in word:
            ans += abs(idx_map[c] - i)
            i = idx_map[c]
        return ans

    def countElements(self, arr: List[int]) -> int:
        shown = [False] * 1002
        for v in arr:
            shown[v] = True
        res = 0
        for v in arr:
            if shown[v + 1]:
                res += 1
        return res

    def smallestCommonElement(self, mat: List[List[int]]) -> int:
        m, n = len(mat), len(mat[0])
        counter = Counter()
        for i in range(m):
            for j in range(n):
                counter[mat[i][j]] += 1
        res = float("inf")
        for k, v in counter.items():
            if v == m:
                res = min(res, k)
        return -1 if res == float("inf") else res

    def validWordSquare(self, words: List[str]) -> bool:
        n = len(words)
        for i in range(n):
            if len(words[i]) > n:
                return False
            words[i] += " " * (n - len(words[i]))
        for i in range(n):
            for j in range(i + 1, n):
                if words[i][j] != words[j][i]:
                    return False
        return True

    def findLonelyPixel(self, picture: List[List[str]]) -> int:
        m, n = len(picture), len(picture[0])
        rows, cols = [0] * m, [0] * n
        for i in range(m):
            for j in range(n):
                if picture[i][j] == "B":
                    rows[i] += 1
                    cols[j] += 1
        res = 0
        for i in range(m):
            if rows[i] != 1:
                continue
            for j in range(n):
                if picture[i][j] == "B" and cols[j] == 1:
                    res += 1
        return res

    def multiply(self, mat1: List[List[int]], mat2: List[List[int]]) -> List[List[int]]:
        # A = np.array(mat1)
        # B = np.array(mat2)
        # return A.dot(B).tolist()
        # # definition
        # m, k, n = len(mat1), len(mat1[0]), len(mat2[0])
        # res = [[0] * n for _ in range(m)]
        # for i in range(m):
        #     for j in range(n):
        #         res[i][j] = sum(mat1[i][t] * mat2[t][j] for t in range(k))
        # return res
        # left product，左乘，行乘
        m, k, n = len(mat1), len(mat1[0]), len(mat2[0])

        def add(row_vec1, row_vec2):
            for i in range(n):
                row_vec1[i] += row_vec2[i]

        def scale(row_vec, k):
            return [k * v for v in row_vec]

        res = []
        for i in range(m):
            rowi = [0] * n
            for t in range(k):
                if mat1[i][t] == 0:
                    continue
                add(rowi, scale(mat2[t], mat1[i][t]))
            res.append(rowi)
        return res

    def countLetters(self, s: str) -> int:
        n = len(s)
        i = 0
        while i < n:
            j = i
            while j < n and s[j] == s[i]:
                j += 1
            length = j - i
            i = j
            res += (length * (length + 1)) // 2
        return res

    def findNumbers(self, nums: List[int]) -> int:
        res = 0
        for x in nums:
            if x <= 10 < 100 or 1000 <= x < 10000:
                res += 1
        return res


nums = [1, 3, 2, 3, 3]
k = 2
print(Solution().countSubarrays(nums, k))
